Zur Komplexität der Reduzierbarkeit von Open-Shop-Plänen

Das Open-Shop Schedulingproblem liegt in der Komplexitätsklasse NP-complete. Ein möglicher Weg zur Entwicklung von neuen Heuristiken zur Lösung von Open-Shop Problemen ist die Einschränkung des Suchraums auf effiziente Lösungen. Aus diesem Ansatz entwickelte sich die Theorie der Reduzierbarkeit von Open-Shop Plänen. Ein Plan heißt irreduzibel, wenn es keinen anderen Plan gibt, der bei beliebiger Wahl der Bearbeitungszeiten einen besseren Zielfunktionswert liefert. In dieser Arbeit wird die Komplexität des Reduzierbarkeitsproblems (REDUCIBILITY) untersucht. Bekannt ist die Zugehörigkeit von REDUCIBILITY zu NP. Untersucht werden die Bedingungen, unter denen das komplementäre Problem IRREDUCIBILITY in NP, und damit in NP ∩ co-NP = ZPP*, oder sogar in P liegt. Es wird ein Algorithmus vorgestellt, der reduzierbare Pläne nichtdeterministisch reduziert, und irreduzible Pläne nur unter sehr engen Voraussetzungen nicht als irreduzibel erkennen kann. Die Hinweise auf die Zugehörigkeit von IRREDUCIBILITY zu P oder zu NP- incomplete = NP − (P + NP-complete) werden diskutiert.